package com.hy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二叉树的所有路径
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 * author: Mr.Du
 * Date: 2023/9/12
 * Time: 10:10
 */
public class BinaryTreePaths {

    List<String> res = new ArrayList<>();
    LinkedList<TreeNode> path = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) return res;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root){
        if(root == null) return;
        path.add(root);
        if(root.left == null && root.right == null){
            StringBuffer sb = new StringBuffer();
            for(int i = 0;i < path.size();i++){
                if(i != path.size() - 1)
                    sb.append(path.get(i).val + "->");
                else sb.append(path.get(i).val);
            }
            res.add(sb.toString());
            path.removeLast();
            return;
        }
        dfs(root.left);
        dfs(root.right);
        path.removeLast();
    }
}
